package tothello;

import java.util.ArrayList;
import java.util.List;

/**
 * Interesting Puzzle.
 * Fun to solve it and feels good after you solve the issue.
 * @author Seabook
 *
 */
public class Tothello {
	private static final String RED_TURN = "Red";
	private static final String Black_TURN = "Black";

	private Board board = new Board();
	private int bestBoardNum = 0;
	private int turnedNum = 0;
	private int orgNum = 0;

	private List<BoardWrapper> triedBoards = new ArrayList<BoardWrapper>();

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Tothello to = new Tothello();
		String[] redPieces = new String[] { "C2", "C3", "C4", "C5", "D4", "E4",
				"F2", "F3", "F4", "F5", "G6" };
		String blackPieces[] = new String[] { "B1", "E1", "G1", "C6", "H7",
				"G4" };
		to.bestMove(redPieces, blackPieces, Black_TURN);

	}

	public int bestMove(String[] redPieces, String[] blackPieces,
			String whoseTurn) {
		int redPiecesCount = redPieces.length;
		int blackPiecesCount = blackPieces.length;

		if (redPiecesCount > 50) {
			throw new RuntimeException("Too many red pieces.");
		}

		if (blackPiecesCount > 50) {
			throw new RuntimeException("Too many black pieces.");
		}

		if (redPiecesCount + blackPiecesCount > 63) {
			throw new RuntimeException("No more space to move.");
		}

		char pieceColor = Board.BLACK_PIECE;
		if (Black_TURN.equals(whoseTurn)) {
			pieceColor = Board.BLACK_PIECE;
		} else if (RED_TURN.equals(whoseTurn)) {
			pieceColor = Board.RED_PIECE;
		} else
			throw new RuntimeException("No such piece color!!!");

		board.initPieces(redPieces, Board.RED_PIECE);
		board.initPieces(blackPieces, Board.BLACK_PIECE);

		orgNum = board.getTotalPiecesNoByColor(pieceColor);
		System.out
				.println("================= Print Init Board =========================");
		printBoard(board);

		System.out.println();
		System.out.println();

		tryBestMove(pieceColor);
		System.out
				.println("================= Print Best Tried Board =========================");
		
		BoardWrapper bestBoardWrapper = triedBoards.get(bestBoardNum);
		Board bestBoard = bestBoardWrapper.getBoard();
		int bestX =  bestBoardWrapper.getTriedX();
		int bestY = bestBoardWrapper.getTriedY();
		
		bestBoard.board[bestX][bestY] = '+';
		
		System.out.println("BestStep: " + Board.transferedLoctionFromIntArray2String(bestX, bestY));
		printBoard(bestBoard);

		System.out.println("turnedNum: " + turnedNum);

		return turnedNum;
	}

	/**
	 *  Consider 3 possibilities:
	 *  1) Horizontal
	 *  2) Vertical
	 *  3) Diagnoal
	 *  
	 *  copy all the calculated board into the list
	 *  
	 *  compare all the board later.
	 * @param pieceColor
	 */
	private void tryBestMove(char pieceColor) {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if (board.getBoard()[i][j]!=Board.EMPTY_PIECE) {
					continue;
				}
				Board clonedBoard = cloneBoard(board);
				thinkTOturn(clonedBoard, pieceColor, i, j);
				BoardWrapper boardWrapper = new BoardWrapper(clonedBoard, i, j);
				triedBoards.add(boardWrapper);
			}
		}

		for (int x = 0; x < triedBoards.size(); x++) {
			int countTurnedNum = 0;
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					if (pieceColor == triedBoards.get(x).getBoard().getBoard()[i][j]) {
						countTurnedNum++;
					}
				}
			}

			if (countTurnedNum > turnedNum) {
				bestBoardNum = x;
				turnedNum = countTurnedNum;
			}
		}
		
		turnedNum -= orgNum; 
	}

	/*
	 * Recursive this to solve all the hidden possibilities
	 */
	private void thinkTOturn(Board board, char pieceColor, int x, int y) {
		tryHorizontal(board, pieceColor, x, y);
		tryVertical(board, pieceColor, x, y);
		tryDiagonal(board, pieceColor, x, y);
	}

	/*
	 * 4 possibles
	 * 1) left - up
	 * 2) right - up
	 * 3) left - down
	 * 4) right - down
	 */
	private void tryDiagonal(Board board, char pieceColor, int x, int y) {
		int nextX1 = -1;
		int nextY1 = -1;
		int nextX2 = -1;
		int nextY2 = -1;
		int nextX3 = -1;
		int nextY3 = -1;
		int nextX4 = -1;
		int nextY4 = -1;

		// right-up corner
		int count = 0;
		for (int i = x + 1; i < 8; i++) {
			count ++;
			
			int tmpX = i;
			int tmpY = y - count;

			if (tmpY >=0 && Board.EMPTY_PIECE == board.getBoard()[tmpX][tmpY]) {
				break;
			}

			if (tmpY >=0 && pieceColor == board.getBoard()[tmpX][tmpY]) {
				nextX1 = tmpX;
				nextY1 = tmpY;
				break;
			}
		}

		count = 0;
		if (nextX1 != -1 && nextX1 >= x && nextX1 < 8 && nextY1 != -1
				&& nextY1 >= 0 && nextY1 < y) {
			for (int i = x + 1; i < nextX1; i++) {
				count ++;
				int tmpX = i;
				int tmpY = y - count;
				board.getBoard()[tmpX][tmpY] = pieceColor;
				thinkTOturn(board, pieceColor, tmpX, tmpY);
			}
		}
		
		// left-up corner
		count = 0;
		for (int i = x - 1; i >= 0; i--) {
			count ++;
			int tmpX = i;
			int tmpY = y - count;

			if (tmpY >= 0 && Board.EMPTY_PIECE == board.getBoard()[tmpX][tmpY]) {
				break;
			}

			if (tmpY >= 0 && pieceColor == board.getBoard()[tmpX][tmpY]) {
				nextX2 = tmpX;
				nextY2 = tmpY;
				break;
			}
		}

		count = 0;
		if (nextX2 != -1 && nextX2 >= 0 && nextX2 < x && nextY2 != -1
				&& nextY2 >= 0 && nextY2 < y) {
			for (int i = x - 1; i > nextX2; i--) {
				count ++;
				int tmpX = i;
				int tmpY = y - count;
				board.getBoard()[tmpX][tmpY] = pieceColor;
				thinkTOturn(board, pieceColor, tmpX, tmpY);
			}
		}
		
		
		// right-down corner
		count = 0;
		for (int i = x + 1; i < 8; i++) {
			count ++;
			int tmpX = i;
			int tmpY = y + count;

			if (tmpY < 8 && Board.EMPTY_PIECE == board.getBoard()[tmpX][tmpY]) {
				break;
			}

			if (tmpY < 8 && pieceColor == board.getBoard()[tmpX][tmpY]) {
				nextX3 = tmpX;
				nextY3 = tmpY;
				break;
			}
		}

		count = 0;
		if (nextX3 != -1 && nextX3 > x && nextX3 < 8 && nextY3 != -1
				&& nextY3 > y && nextY3 < 8) {
			for (int i = x + 1; i < nextX3; i++) {
				count++;
				int tmpX = i;
				int tmpY = y + count;
				board.getBoard()[tmpX][tmpY] = pieceColor;
				thinkTOturn(board, pieceColor, tmpX, tmpY);
			}
		}
		
		
		// left-down corner
		count = 0;
		for (int i = x - 1; i >= 0; i--) {
			count++;
			int tmpX = i;
			int tmpY = y + count;

			if (tmpY < 8 && Board.EMPTY_PIECE == board.getBoard()[tmpX][tmpY]) {
				break;
			}

			if (tmpY < 8 && pieceColor == board.getBoard()[tmpX][tmpY]) {
				nextX4 = tmpX;
				nextY4 = tmpY;
				break;
			}
		}

		count = 0;
		if (nextX4 != -1 && nextX4 >= 0 && nextX4 < x && nextY4 != -1
				&& nextY4 > y && nextY4 < 8) {
			for (int i = x - 1; i > nextX4; i--) {
				count ++;
				int tmpX = i;
				int tmpY = y + count;
				board.getBoard()[tmpX][tmpY] = pieceColor;
				thinkTOturn(board, pieceColor, tmpX, tmpY);
			}
		}
		
	}

	/**
	 * 2 possibles
	 * up
	 * down
	 * 
	 * @param board
	 * @param pieceColor
	 * @param x
	 * @param y
	 */
	private void tryVertical(Board board, char pieceColor, int x, int y) {

		int nextPosition = -1;
		int previousPosition = -1;

		// Check up
		for (int j = y + 1; j < 8; j++) {
			if (Board.EMPTY_PIECE == board.getBoard()[x][j]) {
				break;
			}

			if (pieceColor == board.getBoard()[x][j]) {
				nextPosition = j;
				break;
			}
		}

		if (nextPosition != -1 && nextPosition >= 0 && nextPosition < 8) {
			for (int j = y + 1; j < nextPosition; j++) {
				board.getBoard()[x][j] = pieceColor;
				thinkTOturn(board, pieceColor, x, j);
			}
		}

		// Check down
		for (int j = y - 1; j >= 0; j--) {
			if (Board.EMPTY_PIECE == board.getBoard()[x][j]) {
				break;
			}

			if (pieceColor == board.getBoard()[x][j]) {
				previousPosition = j;
				break;
			}
		}

		if (previousPosition != -1 && previousPosition >= 0
				&& previousPosition < 8) {
			for (int j = y - 1; j > previousPosition; j--) {
				board.getBoard()[x][j] = pieceColor;
				thinkTOturn(board, pieceColor, x, j);
			}
		}

	}

	/**
	 * 2 possibles
	 * 
	 * right
	 * left
	 * 
	 * 
	 * @param board
	 * @param pieceColor
	 * @param x
	 * @param y
	 */
	private void tryHorizontal(Board board, char pieceColor, int x, int y) {
		int nextPosition = -1;
		int previousPosition = -1;

		// Check Right
		for (int i = x + 1; i < 8; i++) {
			if (Board.EMPTY_PIECE == board.getBoard()[i][y]) {
				break;
			}

			if (pieceColor == board.getBoard()[i][y]) {
				nextPosition = i;
				break;
			}
		}

		if (nextPosition != -1 && nextPosition >= 0 && nextPosition < 8) {
			for (int i = x + 1; i < nextPosition; i++) {
				board.getBoard()[i][y] = pieceColor;
				thinkTOturn(board, pieceColor, i, y);
			}
		}

		// Check Left
		for (int i = x - 1; i >= 0; i--) {
			if (Board.EMPTY_PIECE == board.getBoard()[i][y]) {
				break;
			}

			if (pieceColor == board.getBoard()[i][y]) {
				previousPosition = i;
				break;
			}
		}

		if (previousPosition != -1 && previousPosition >= 0
				&& previousPosition < 8) {
			for (int i = x - 1; i > previousPosition; i--) {
				board.getBoard()[i][y] = pieceColor;
				thinkTOturn(board, pieceColor, i, y);
			}
		}

	}

	public void printBoard(Board board) {
		for (int j = 0; j < 8; j++) {
			for (int i = 0; i < 8; i++) {
				System.out.print(board.getBoard()[i][j] + " ");
			}
			System.out.println();
		}
	}

	public Board cloneBoard(Board board) {
		return new Board(board.getBoard());
	}

}

class BoardWrapper {
	private Board board;
	private int triedX;
	private int triedY;
	
	public BoardWrapper() {
	}

	public BoardWrapper(Board board, int triedX, int triedY) {
		this.board = board;
		this.triedX = triedX;
		this.triedY = triedY;
	}

	public Board getBoard() {
		return board;
	}

	public void setBoard(Board board) {
		this.board = board;
	}

	public int getTriedX() {
		return triedX;
	}

	public void setTriedX(int triedX) {
		this.triedX = triedX;
	}

	public int getTriedY() {
		return triedY;
	}

	public void setTriedY(int triedY) {
		this.triedY = triedY;
	}
}

class Board {
	char[][] board = new char[8][8];

	public static final char RED_PIECE = 'R';
	public static final char BLACK_PIECE = 'B';
	public static final char EMPTY_PIECE = '-';

	public Board(char[][] board) {
		this.board = new char[8][8];
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				this.board[i][j] = board[i][j];
			}
		}
	}

	public Board() {
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				board[i][j] = EMPTY_PIECE;
			}
		}
	}

	public void initPieces(String[] pieces, char color) {
		for (String piece : pieces) {
			char column = piece.charAt(0);
			char row = piece.charAt(1);

			int x = covertColumn(column, color);
			int y = covertRow(row, color);
			board[x][y] = color;
		}
	}

	private int covertColumn(char column, char color) {
		switch (column) {
		case 'A':
			return 0;
		case 'B':
			return 1;
		case 'C':
			return 2;
		case 'D':
			return 3;
		case 'E':
			return 4;
		case 'F':
			return 5;
		case 'G':
			return 6;
		case 'H':
			return 7;
		default:
			throw new RuntimeException("Column Number Incorrect!!!");
		}
	}

	private int covertRow(char row, char color) {
		int x = Character.getNumericValue(row) - 1;
		if (x < 0 || x >= 8) {
			throw new RuntimeException("Row Number Incorrect!!!");
		}

		return x;
	}

	public int getTotalPiecesNoByColor(char color) {
		int count = 0;
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 8; j++) {
				if (board[i][j] == color) {
					count++;
				}
			}
		}
		return count;
	}

	public char[][] getBoard() {
		return board;
	}

	public void setBoard(char[][] board) {
		this.board = board;
	}
	
	public static String transferedLoctionFromIntArray2String(int x, int y) {
		String xPosition = null;
		switch (x) {
		case 0:
			xPosition =  "A";
			break;
		case 1:
			xPosition =  "B";
			break;
		case 2:
			xPosition =  "C";
			break;
		case 3:
			xPosition =  "D";
			break;
		case 4:
			xPosition = "E";
			break;
		case 5:
			xPosition = "F";
			break;
		case 6:
			xPosition = "G";
			break;
		case 7:
			xPosition = "H";
			break;
		default:
			throw new RuntimeException("Column Number Incorrect!!!");
		}
		
		return (xPosition + y);
	}
}
